1296D - Fight with Monsters - CodeForces Solution

//Practice is the only shortcut to improve
#include<bits/stdc++.h>
using namespace std;

#define for0(i, n) for(int i=0; i<n; i++)
#define for1(i, n) for(int i=1; i<=n; i++)
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define vi vector<int>
#define MOD 1000000007
#define nline "\n"
#define ff first
#define ss second
#define INF 1e18
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define debug(x)
#endif

void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(lld t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}

template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}

//graph
int findParent(int node,vector<int>& par){if(par[node]==node) return node; return par[node]=findParent(par[node],par);}
void Union(int u,int v,vector<int>& par,vector<int>& size){int pu=findParent(u,par);int pv=findParent(v,par);if(pu==pv) return;if(size[pu]>=size[pv]){par[pv]=pu;size[pu]++;}else{par[pu]=pv;size[pv]++;}} 

//segment tree -- Ranged Queries
void build_ranged_sum(vi& a, int v, int tl, int tr,vi& t)
{
    if (tl == tr)t[v] = a[tl];
    else {int tm = (tl + tr) / 2;
    build_ranged_sum(a, v*2, tl, tm,t);
    build_ranged_sum(a, v*2+1, tm+1, tr,t);
    t[v] = t[v*2] + t[v*2+1];
    }
}
int ranged_sum(int v, int tl, int tr, int l, int r,vi& t)
{
    if (l > r) return 0;
    if (l == tl && r == tr) {return t[v];}
    int tm = (tl + tr) / 2;
    return ranged_sum(v*2, tl, tm, l, min(r, tm),t)+ ranged_sum(v*2+1, tm+1, tr, max(l, tm+1), r,t);
}
void update(int v, int tl, int tr, int pos, int new_val,vi& t) 
{
    if (tl == tr) {t[v] = new_val;} 
    else {int tm = (tl + tr) / 2;
    if (pos <= tm) update(v*2, tl, tm, pos, new_val,t);
    else update(v*2+1, tm+1, tr, pos, new_val,t);
    t[v] = t[v*2] + t[v*2+1];
    }
}
/*---------------------------------------------------------------------------------------------------------------------------*/
ll gcd(ll a, ll b) {if (b > a) {return gcd(b, a);} if (b == 0) {return a;} return gcd(b, a % b);}
ll expo(ll a, ll b, ll mod) {ll res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;}
ll mod_add(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}
ll mod_mul(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}
ll mod_sub(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a - b) % m) + m) % m;}
ll mminvprime(ll a, ll b) {return expo(a, b - 2, b);}
ll mod_div(ll a, ll b, ll m) {a = a % m; b = b % m; return (mod_mul(a, mminvprime(b, m), m) + m) % m;}  //only for prime m
vector<ll> sieve(int n) {int*arr = new int[n + 1](); vector<ll> vect; for (int i = 2; i <= n; i++)if (arr[i] == 0) {vect.push_back(i); for (int j = 2 * i; j <= n; j += i)arr[j] = 1;} return vect;}
/*---------------------------------------------------------------------------------------------------------------------------*/
/*  NOTES: 
    -> a << n = a * pow(2, n)
    -> a >> n = a / pow(2, n)
    -> if(n&1) odd else even
    -> min no of bits to change a to b ==> a ^ b 
        ex a = 11, b = 15, a = 1011, b = 1111, a^b = 0100
    -> Count the set bits ==> while(n){ cnt += (n&1), n = n >> 1}
    -> To remove the last set bit ==> n & (n-1) 
        ex a = 13, 1101, a & (a-1), 1101 & 1100 = 1100
    -> To extract the ith bit we use mask ==> x = n & (1 << i)
        ex n = 13, 1101, i = 2, so 1 << 2 = 0100, so we get 4
    -> Changing the ith bit ==> n | (1 << i)
        ex n = 13, i = 2, 1101 | (1<<2), 1101|0010 = 1111
    -> Clearing the ith bit ==> n & (~(1<<i)) 
        ex n = 13, i = 2, 1101 & (~(1<<i)), 1101 & (1011) = 1001
    -> To get first set bit y = x&(~(x-1))
    -> 
*/
void solve(){
    int n, k, a, b, cnt = 0; cin>>n>>a>>b>>k;
    vi vec(n), freq; 
    for0(i,n){
        cin>>vec[i]; 
        int x = vec[i]%(a+b);
        if(!x){
            freq.pb(b/a + (b%a != 0));
        }else if(x > a){
            int rem = x - a;
            freq.pb(rem/a + (rem%a != 0));
        }else cnt++;
    }
    sort(all(freq)); 
    for0(i, sz(freq)){
        if(freq[i] <= k) cnt++, k -= freq[i];
        else break;
    }
    cout<<cnt<<'\n';
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("Error.txt", "w", stderr);
#endif
    fast;
    int t = 1; 
    // cin>>t;
    while(t--) solve();
    return 0;
}